/**
 * @file 121.BuyAndSellStock.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-27
 *
 * @copyright Copyright (c) 2021
 *
 * 买卖股票
 * 121.买卖股票最佳时机   -- 可贪心
 * 122.买卖股票最佳时机II -- 可贪心
 * 123.买卖股票最佳时机III
 * 188.买卖股票最佳时机IV
 * 309.最佳买卖股票时机含冷冻期  难 -- 暂略
 * 714.买卖股票最佳时机含手续费 -- 贪心可以但没必要
 */

#include <cmath>

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class Solution
{
public:
    // 买卖股票I：只能买卖一次
    int maxProfitI(vector<int> &prices)
    {
        // 首先对此提来说，dp非最优解，但通用所有股票问题
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        // 最后返回dp[n-1][1]
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入(只能买卖一次)
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
#if 0
        // 贪心，维护前i日最低价格和当前最大利润
        int cost = 1e5;
        int profit = 0;
        for (auto &price : prices) {
            cost = min(cost, price);            // 前i日最低价格
            profit = max(profit, price - cost); // 当前卖不卖？
        }
        return profit;
#endif
    }
    // 买卖股票II：买卖不限次数
    int maxProfitII(vector<int> &prices)
    {
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入(前一天不持有+当天买入)
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
#if 0
        // 贪心：只要每天利润就买卖
        int n = prices.size();
        int profit = 0;
        for (int i = 1; i < n; ++i) {
            profit += max(prices[i] - prices[i - 1], 0);
        }
        return profit;
#endif
    }
    // 买卖股票III，至多完成2次买卖
    int maxProfitIII(vector<int> &prices)
    {
        // dp[i][0] 第i天无操作所得最多现金
        // dp[i][1] 第i天第一次买入所得最多现金
        // dp[i][2] 第i天第一次卖出所得最多现金
        // dp[i][3] 第i天第二次买入所得最多现金
        // dp[i][4] 第i天第二次卖出所得最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[n - 1][4];
    }
    // 买卖股票IV，至多完成k次买卖
    int maxProfitIV(int k, vector<int> &prices)
    {
        // dp[i][0] 第i天无操作所得最多现金
        // dp[i][1] 第i天第一次买入
        // dp[i][2] 第i天第一次卖出
        // dp[i][3] 第i天第二次买入
        // dp[i][4] 第i天第二次卖出
        // ... dp[i][2*k-1] 第i天第k次买入
        // ... dp[i][2*k]   第i天第k次卖出
        int n = prices.size();
        if (0 == n) {
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(2 * k + 1, 0));
        // dp[0][1] = -prices[0];
        // dp[0][3] = -prices[0];
        // ...dp[0][2*k+1] = -prices[0];
        for (int j = 0; j < k; ++j) {
            dp[0][2 * j + 1] = -prices[0];
        }
        for (int i = 1; i < n; ++i) {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j < 2 * k + 1; ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (int)pow(-1, j) * prices[i]);
            }
        }
        return dp[n - 1][2 * k];
    }
    // 买卖股票含手续费：买卖不限次数 卖出时减去手续费
    int maxProfitFee(vector<int> &prices, int fee)
    {
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入(前一天不持有+当天买入)
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n - 1][1];
    }
};

void test121()
{
    vector<int> nums1 = {7, 1, 5, 3, 6, 4};
    vector<int> nums2 = {7, 6, 4, 3, 1};
    cout << Solution().maxProfitI(nums1) << endl;
    cout << Solution().maxProfitI(nums2) << endl;
}

void test122()
{
    vector<int> nums1 = {7, 1, 5, 3, 6, 4};
    vector<int> nums2 = {1, 2, 3, 4, 5};
    vector<int> nums3 = {7, 6, 4, 3, 1};
    cout << Solution().maxProfitII(nums1) << endl;
    cout << Solution().maxProfitII(nums2) << endl;
    cout << Solution().maxProfitII(nums3) << endl;
}

void test123()
{
    vector<int> nums1 = {3, 3, 5, 0, 0, 3, 1, 4};
    vector<int> nums2 = {1, 2, 3, 4, 5};
    vector<int> nums3 = {7, 6, 4, 3, 1};
    vector<int> nums4 = {1};
    cout << Solution().maxProfitIII(nums1) << endl;
    cout << Solution().maxProfitIII(nums2) << endl;
    cout << Solution().maxProfitIII(nums3) << endl;
    cout << Solution().maxProfitIII(nums4) << endl;
}

void test188()
{
    vector<int> nums1 = {3, 3, 5, 0, 0, 3, 1, 4};
    vector<int> nums2 = {1, 2, 3, 4, 5};
    vector<int> nums3 = {7, 6, 4, 3, 1};
    vector<int> nums4 = {3, 2, 6, 5, 0, 3};
    cout << Solution().maxProfitIV(2, nums1) << endl;
    cout << Solution().maxProfitIV(2, nums2) << endl;
    cout << Solution().maxProfitIV(1, nums3) << endl;
    cout << Solution().maxProfitIV(3, nums4) << endl;
}

void test714()
{
    vector<int> nums1 = {1, 3, 2, 8, 4, 9};
    vector<int> nums2 = {1, 3, 7, 5, 10, 3};
    cout << Solution().maxProfitFee(nums1, 2) << endl;
    cout << Solution().maxProfitFee(nums2, 3) << endl;
}

int main()
{
    // test121();
    // test122();
    // test123();
    // test188();
    test714();
    return 0;
}